#include "redblacktree.h"
#include <stdio.h>
#include <stdlib.h>

RBTNode* Nil;

void __attribute__((constructor)) rbtree_prepare() {
    Nil = rbtree_createNode(0);
    Nil->Color = BLACK;
}

RBTNode* parentOf(RBTNode* p) {
    return (p == NULL ? NULL : p->Parent);
}

RBTNode* leftOf(RBTNode* p) {
    return (p == NULL ? NULL : p->Left);
}

RBTNode* rightOf(RBTNode* p) {
    return (p == NULL ? NULL : p->Right);
}

int colorOf(RBTNode* p) {
    return (p == NULL?BLACK : p->Color);
}

void setColor(RBTNode* p, int color) {
    if (p != NULL) p->Color = color;
}

RBTNode* rbtree_createNode(KEYTYPE NewData) {
    RBTNode* NewNode = (RBTNode*)malloc(sizeof(RBTNode));
    NewNode->Parent = NewNode->Left = NewNode->Right = NULL;
    NewNode->key = NewData;
    NewNode->Color = BLACK;
    return NewNode;
}

void rbtree_destroyNode(RBTNode* Node) {
    free(Node);
}

void rbtree_destroyTree(RBTNode* Tree) {

    if (Tree == NULL) {
        return;
    }
    if (Tree->Right != Nil)
        rbtree_destroyTree(Tree->Right);
    if (Tree->Left != Nil)
        rbtree_destroyTree(Tree->Left);

    Tree->Left = Nil;
    Tree->Right = Nil;
    rbtree_destroyNode(Tree);
}

RBTNode* rbtree_searchNode(RBTNode* Tree, KEYTYPE Target) {
    if (Tree == Nil) return NULL;

    if (Tree->key> Target) {
        return rbtree_searchNode(Tree->Left, Target);
    }
    else if (Tree->key< Target) {
        return rbtree_searchNode(Tree->Right, Target);
    }
    else {
        return Tree; // found
    }
}

//가장 작은 값을 가진 Node를 찾는다.
RBTNode* rbtree_searchMinNode(RBTNode* Tree) {
    if (Tree == Nil) return Nil;

    if (Tree->Left == Nil) {
        return Tree;
    }
    else {
        return rbtree_searchMinNode(Tree->Left);
    }
}

void rbtree_insertNode(RBTNode** Root, RBTNode* NewNode) {

    RBTNode* Tree = *Root;

    NewNode->Color = RED;
    NewNode->Left = Nil;
    NewNode->Right = Nil;

    if ((*Root) == NULL) {
        (*Root) = NewNode;
        return;
    }

    while(1) {
        if ((Tree)->key>= NewNode->key) {
            if ((Tree)->Left == Nil) {
                (Tree)->Left = NewNode;
                NewNode->Parent = (Tree);
                rbtree_rebuildAfterInsert(Root, NewNode);
                return;
            }
            else {
                (Tree) = (Tree)->Left;
            }
        }
        else {
            if ((Tree)->Right == Nil) {
                (Tree)->Right = NewNode;
                NewNode->Parent = (Tree);
                rbtree_rebuildAfterInsert(Root, NewNode);
                return;
            }
            else {
                (Tree) = (Tree)->Right;
            }
        }
    }
}

void rbtree_rotateLeft(RBTNode** Root, RBTNode* Parent) {
    RBTNode* RightChild = Parent->Right;

    Parent->Right = RightChild->Left;

    if (RightChild->Left != Nil) { RightChild->Left->Parent = Parent; }

    RightChild->Parent = Parent->Parent;

    if (Parent->Parent == NULL) {
        (*Root) = RightChild;
    }
    else if (Parent->Parent->Left == Parent) {
        Parent->Parent->Left = RightChild;
    }
    else {
        Parent->Parent->Right = RightChild;
    }

    RightChild->Left = Parent;
    Parent->Parent = RightChild;
}

void rbtree_rotateRight(RBTNode** Root, RBTNode* Parent) {
    RBTNode* LeftChild = Parent->Left;

    Parent->Left = LeftChild->Right;

    if (LeftChild->Right != Nil) { LeftChild->Right->Parent = Parent; }

    LeftChild->Parent = Parent->Parent;

    if (Parent->Parent == NULL) {
        (*Root) = LeftChild;
    }
    else if (Parent->Parent->Right == Parent) {
        Parent->Parent->Right = LeftChild;
    }
    else {
        Parent->Parent->Left = LeftChild;
    }

    LeftChild->Right = Parent;
    Parent->Parent = LeftChild;
}

void rbtree_rebuildAfterInsert(RBTNode** Root, RBTNode* X) {

    while (X != NULL && X != (*Root) && X->Parent->Color == RED) {
        if (parentOf(X) == leftOf(parentOf(parentOf(X)))) {
            RBTNode* Uncle = rightOf(parentOf(parentOf(X)));
            if (Uncle->Color == RED) {
                X->Parent->Color 			= BLACK;
                Uncle->Color 				= BLACK;
                X->Parent->Parent->Color 	= RED;
                X = X->Parent->Parent;
            }
            else {
                if (X == X->Parent->Right) {
                    X = X->Parent;
                    rbtree_rotateLeft(Root, X);
                }

                X->Parent->Color 			= BLACK;
                X->Parent->Parent->Color 	= RED;

                if (parentOf(parentOf(X)) != NULL) {
                    rbtree_rotateRight(Root, X->Parent->Parent);
                }
            }
        }
        else {
            RBTNode* Uncle = leftOf(parentOf(parentOf(X)));
            if (colorOf(Uncle) == RED) {
                X->Parent->Color 			= BLACK;
                Uncle->Color 				= BLACK;
                X->Parent->Parent->Color 	= RED;
                X = X->Parent->Parent;
            }
            else {
                if (X == X->Parent->Left) {
                    X = X->Parent;
                    rbtree_rotateRight(Root, X);
                }

                setColor(parentOf(X), BLACK);
                setColor(parentOf(parentOf(X)), RED); 
                if (parentOf(parentOf(X)) != NULL) {
                    rbtree_rotateLeft(Root, X->Parent->Parent);
                }
            }
        }
    }

    (*Root)->Color = BLACK;
}

RBTNode* rbtree_removeNode(RBTNode** Root, KEYTYPE Data) {
    RBTNode* Removed = NULL;
    RBTNode* replacement = NULL;
    RBTNode* Target = rbtree_searchNode( (*Root), Data);

    if (Target == NULL)
        return NULL;

    if (Target->Left == Nil || Target->Right == Nil) {
        Removed = Target;
    }
    else {
        // 지워질 노드는 left/right 모두 가지고 있다.
        // 이럴경우 오른쪽 자식의 가장 작은값을 가진 노드가 여기로 오고 지워질 노드는 오른쪽 자식중 가장 작은값을 가진 노드로 교체한다.
        Removed = rbtree_searchMinNode(Target->Right);
        // Target과 오른쪽 자식중 가장 작은것(이게 Target 자리로 이동할것)의 content를 여기서 교체
        Target->key = Removed->key;
    }

    // 자리를 대신 차지할 node를 선택(왼쪽 것이 있으면 왼쪽 그렇지 않으면 오른쪽)
    if (Removed->Left != Nil) {
        replacement = Removed->Left;
    }
    else {
        replacement = Removed->Right;
    }
    // 후계자의 부모도 맞춰준다.
    replacement ->Parent = Removed->Parent;

    if (Removed->Parent == NULL) { // 부모가 NULL이면 그게 root
        (*Root) = replacement;
    }
    else {
        // 제거될 노드로 올 replacement와 제거될 노드의 부모를 연결한다.
        if (Removed == Removed->Parent->Left) { //제거될 노드가 왼쪽자식
            Removed->Parent->Left = replacement;
        }
        else { //제거될 노드가 오른쪽 자식
            Removed->Parent->Right = replacement;
        }
    }

    if (Removed->Color == BLACK) {
        rbtree_rebuildAfterRemove(Root, replacement);
    }

    return Removed;
}

RBTNode* rbtree_removeNode2(RBTNode** Root, RBTNode* Target) {
    RBTNode* Removed = NULL;
    RBTNode* replacement= NULL;

    if (Target == NULL)
        return NULL;

    if (Target->Left == Nil || Target->Right == Nil) {
        Removed = Target;
    }
    else {
        Removed = rbtree_searchMinNode(Target->Right);
        Target->key= Removed->key;
    }

    if (Removed->Left != Nil) {
        replacement = Removed->Left;
    }
    else {
        replacement = Removed->Right;
    }

    replacement ->Parent = Removed->Parent;

    if (Removed->Parent == NULL) {
        (*Root) = replacement;
    }
    else {
        if (Removed == Removed->Parent->Left) {
            Removed->Parent->Left = replacement;
        }
        else {
            Removed->Parent->Right = replacement;
        }
    }

    if (Removed->Color == BLACK) {
        rbtree_rebuildAfterRemove(Root, replacement);
    }

    return Removed;
}



void rbtree_rebuildAfterRemove(RBTNode** Root,/*replacement*/ RBTNode* Successor) {
    RBTNode* Sibling = NULL;

    while (Successor->Parent != NULL && Successor->Color == BLACK) {
        if (Successor == leftOf(parentOf(Successor))) {
            Sibling = rightOf(parentOf(Successor));

            if (colorOf(Sibling) == RED) {
                Sibling->Color = BLACK;
                setColor(parentOf(Successor), RED);
                rbtree_rotateLeft(Root, Successor->Parent);
                Sibling = rightOf(parentOf(Successor));
            }
            else {
                if (colorOf(leftOf(Sibling)) == BLACK && colorOf(rightOf(Sibling)) == BLACK) {
                    Sibling->Color = RED;
                    Successor = Successor->Parent;
                }
                else {
                    //if (Sibling->Left->Color == RED) {
                    if (colorOf(leftOf(Sibling)) == RED) {
                        Sibling->Left->Color = BLACK;
                        Sibling->Color = RED;

                        rbtree_rotateRight(Root, Sibling);
                        Sibling = Successor->Parent->Right;
                    }

                    Sibling->Color = Successor->Parent->Color;
                    Successor->Parent->Color = BLACK;
                    Sibling->Right->Color = BLACK;
                    rbtree_rotateLeft(Root, Successor->Parent);
                    Successor = (*Root);
                }
            }
        }
        else {
            Sibling = leftOf(parentOf(Successor)); 
            if (colorOf(Sibling) == RED) {
                Sibling->Color = BLACK;
                Successor->Parent->Color = RED;
                rbtree_rotateRight(Root, Successor->Parent);
                Sibling = leftOf(parentOf(Successor));
            }
            else {
                if (colorOf(rightOf(Sibling)) == BLACK && colorOf(leftOf(Sibling)) == BLACK) {
                    Sibling->Color = RED;
                    Successor = Successor->Parent;
                }
                else {
                    if (colorOf(rightOf(Sibling)) == RED) {
                        setColor(rightOf(Sibling), BLACK);
                        Sibling->Color = RED;

                        rbtree_rotateLeft(Root, Sibling);
                        Sibling = leftOf(parentOf(Successor)); 
                    }
                    Sibling->Color = Successor->Parent->Color;
                    Successor->Parent->Color = BLACK;
                    Sibling->Left->Color = BLACK;

                    rbtree_rotateRight(Root, Successor->Parent);
                    Successor = (*Root);
                }
            }
        }
    }

    Successor->Color = BLACK;
}

void rbtree_printTree(RBTNode* Node, int x, int y, int BlackCount) {
    int i = 0;
    char c = 'X';
    int v = -1;
    char cnt[100];

    if (Node == NULL) printf("something wrong!\n");

    if (Node == Nil) {
        return;
    }

    if (Node->Color == BLACK) {
        BlackCount++;
    }

    if (Node->Parent != NULL) {
        v = Node->Parent->key;
        if (Node->Parent->Left == Node) {
            c = 'L';
        }
        else {
            c = 'R';
        }
    }

    if (Node->Left == Nil && Node->Right == Nil) {
        sprintf(cnt, "blackCount:%d", BlackCount);
    }
    else {
        sprintf(cnt,"   ");
    }

    for (i = 0; i < y; i++) {
        printf("***");
    }

    printf("###Data:%d :%s [%c] (%d,%d) %s\n", Node->key, (Node->Color == RED)?"RED":"BLACK", c, x, y, cnt);

    rbtree_printTree(Node->Left, x-1, y+1, BlackCount);
    rbtree_printTree(Node->Right, x+1, y+1, BlackCount);
}

void rbtree_printTree2(RBTNode* Root, int* numNodes)
{
    int i = 0;
    RBTNode* stack[100];
    int top = 0;
    RBTNode* Node;
    int count = 0;
	*numNodes = 0;

    if (Root == NULL) {
        return;
    }
    
	// push Root
    stack[top++] = Root;
    while (top > 0) {

        Node = stack[--top]; //pop

        if (Node != NULL && Node != Nil) {
			(*numNodes)++;
			stack[top++] = (Node->Left); 	//push left
            stack[top++] = (Node->Right);   //push right
		}
	}
}

void rbtree_makeTreePoints(RBTNode* Root, RBTNode* nodes[], int* numNodes)
{
    int i = 0;
    RBTNode* stack[100];	
    int top = 0;
    RBTNode* Node;
    int id = 1;

    // push Root
    Root->x = Root->y = 0;
    Root->spreadWidth = 50;
    Root->id = id;
    stack[top++] = Root;

#define CALC_SPREAD(x) ((x)*2)/3

    while (top > 0) {

        Node = stack[--top]; //pop
        id++;

        if (Node != NULL && Node != Nil) {

            nodes[(*numNodes)++] = Node;

            Node->Left->x = Node->x - Node->spreadWidth;
            Node->Left->y = Node->y + 1;
            Node->Left->spreadWidth = CALC_SPREAD(Node->spreadWidth);
            Node->Left->id= id++;
            Node->Left->parentId = Node->id;
            stack[top++] = (Node->Left);

            Node->Right->x = Node->x + Node->spreadWidth;
            Node->Right->y = Node->y + 1;
            Node->Right->spreadWidth = CALC_SPREAD(Node->spreadWidth);
            Node->Right->id= id++;
            Node->Right->parentId= Node->id;
            stack[top++] = (Node->Right);            
        }
    }
}

#define MAX_TEST_SRC    30 
#define DELETE_COUNT    8 
int main(int argc,char**argv)
{

    RBTNode* Tree = NULL;
    RBTNode* Node = NULL;

    int values[MAX_TEST_SRC], i;
    int inputCount = 0, nodeCount;

    time_t t = time(NULL);

    srand((t%1000));
    for (i = 0 ; i < MAX_TEST_SRC; i++) {
        values[i] = rand() % 30;
        rbtree_insertNode(&Tree, rbtree_createNode(values[i]));
    }

    // node count check :
    rbtree_printTree(Tree,0,0,0);
    rbtree_printTree2(Tree, &nodeCount);
	if (MAX_TEST_SRC != nodeCount) {
		printf("Error!%d %d!=%d\n", __LINE__, inputCount, nodeCount);
        exit(-1);
	}
	else {
		printf("Check %d pass\n", __LINE__);
	}
    
    for (i = 0; i < DELETE_COUNT; i++) {
        rbtree_removeNode(&Tree, values[i + 2]);
    }

    // node count check after delete 
	rbtree_printTree(Tree,0,0,0);
	rbtree_printTree2(Tree, &nodeCount);
	if ((MAX_TEST_SRC - DELETE_COUNT) != nodeCount) {
		printf("Error!%d %d!=%d\n", __LINE__, inputCount, nodeCount);
        exit(-1);
	}
    else {
        printf("Check %d pass\n", __LINE__);
    }
 
    // clear all
    rbtree_destroyTree(Tree);
    Tree = NULL;

    // insert again
    srand((t%1000));
    for (i = 0 ; i < MAX_TEST_SRC; i++) {
        values[i] = rand() % 30;
        rbtree_insertNode(&Tree, rbtree_createNode(values[i]));
    }
    rbtree_printTree2(Tree, &nodeCount);
	if ((MAX_TEST_SRC) != nodeCount) {
		printf("Error!%d %d!=%d\n", __LINE__, inputCount, nodeCount);
        exit(-1);
	}
    else {
        printf("Check %d pass\n", __LINE__);
    }
 
    // delete all
    for (i = 0 ; i < MAX_TEST_SRC; i++) {
        rbtree_removeNode(&Tree, values[i]);
    }
    rbtree_printTree2(Tree, &nodeCount);
    if (0 != nodeCount) {
        printf("Error!%d %d!=%d\n", __LINE__, inputCount, nodeCount);
        exit(-1);
    }
    else {
        printf("Check %d pass\n", __LINE__);
    }

    printf("all test passed!\n");
    rbtree_destroyTree(Tree);
}



